package someTestExcemple.huaweiOd.unionFindSet;

import java.util.Arrays;
import java.util.Scanner;

//华为OD机试 - 工单调度策略 - 并查集（Java 2024 E卷 200分）
//https://blog.csdn.net/guorui_java/article/details/142664725
//JobOrderSchedulingStrategy
public class odTest {
    /**
     * 工单类，包含SLA时间和积分
     */
    static class Job implements Comparable<Job> {
        int deadline; // 工单的SLA时间
        int score;    // 工单的积分

        public Job(int deadline, int score) {
            this.deadline = deadline;
            this.score = score;
        }

        /**
         * 按照积分从高到低排序，如果积分相同，则按SLA时间从小到大排序
         */
        @Override
        public int compareTo(Job other) {
            if (this.score != other.score) {
                return other.score - this.score; // 降序排列积分
            } else {
                return this.deadline - other.deadline; // 升序排列SLA时间
            }
        }
        @Override
        public String toString() {
            return "Job{" +
                    "deadLine=" + deadline +
                    ", score=" + score +
                    '}';
        }
    }

    /**
     * 并查集（Union-Find）数据结构，用于高效地查找和合并可用的时间槽
     */
    static class UnionFind {
        int[] parent;

        public UnionFind(int size) {
            parent = new int[size + 1];
            for (int i = 0; i <= size; i++) {
                parent[i] = i; // 初始化每个节点的父节点为自己
            }
        }

        /**
         * 查找当前节点的根节点，并进行路径压缩
         * @param x 当前节点
         * @return 根节点
         */
        public int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]); // 路径压缩
            }
            return parent[x];
        }

        /**
         * 合并两个节点
         * @param x 节点x
         * @param y 节点y
         */
        public void union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX != rootY) {
                parent[rootX] = rootY; // 将x的根节点指向y的根节点
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取工单数量N
        int N = scanner.nextInt();
        Job[] jobs = new Job[N];
        int maxDeadline = 0; // 记录最大SLA时间

        // 读取每个工单的SLA时间和积分
        for (int i = 0; i < N; i++) {
            int deadline = scanner.nextInt();
            int score = scanner.nextInt();
            jobs[i] = new Job(deadline, score);
            if (deadline > maxDeadline) {
                maxDeadline = deadline;
            }
        }
        scanner.close();

        // 对工单按照积分从高到低排序
        Arrays.sort(jobs);
        System.out.println(Arrays.toString(jobs));


        // 初始化并查集，大小为最大SLA时间
        UnionFind uf = new UnionFind(maxDeadline);

        long totalScore = 0; // 使用long避免溢出

        // 遍历每个工单，尝试分配到最新的可用时间槽
        for (Job job : jobs) {
            // 查找当前工单的最新可用时间槽
            int availableSlot = uf.find(job.deadline);
            if (availableSlot > 0) {
                totalScore += job.score; // 累加积分
                // 将当前时间槽与前一个时间槽合并，表示该时间槽已被占用
                uf.union(availableSlot, availableSlot - 1);
            }
        }

        // 输出最大积分
        System.out.println(totalScore);
    }
}
